home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 422_02 / misc / hftext.c < prev    next >
C/C++ Source or Header  |  1994-03-20  |  3KB  |  130 lines
  1. /*
  2.  * This is a **very** simple text compression program which performs
  3.  * a "Huffman" encoding of the most common characters in the input file.
  4.  * It is designed to operate as a "unix" style filter, accepting input
  5.  * from "stdin" and writing to "stdout".
  6.  *
  7.  * Syntax:    HFTEXT (Encode | Decode) <input_file >output_file
  8.  *
  9.  * First, the input file is scanned, and a table built up containing
  10.  * the most common characters (highest frequency at the beginning of
  11.  * the table). Then the file is re-read, and any characters which are
  12.  * in the table are replaced with a series of one bits equal in number
  13.  * to its position in the table, followed by a zero bit. Thus, the
  14.  * highest frequency character is encoded into two bits, the second
  15.  * highest is encoded into three bits etc...
  16.  *
  17.  * Characters not occuring in the table are written with a zero bit,
  18.  * followed by the 7 bits of the ASCII character value.
  19.  *
  20.  * Note that this scheme works only on ASCII text files, and becomes *very*
  21.  * confused if the original file contains characters with the high bit set.
  22.  *
  23.  * Compile command: cc hftext -fop
  24.  */
  25. #include <stdio.h>
  26. #include <file.h>
  27. #define    TSIZE    7        /* Size of common character table */
  28.  
  29.     unsigned ftable[256] = 0, ocount = 0;
  30.     unsigned char ctable[TSIZE] = 0, obyte = 0;
  31.  
  32. main(argc, argv)
  33.     int argc;
  34.     char *argv[];
  35. {
  36.     int i, j, k;
  37.  
  38.     stdin  = setbuf(stdin,  1000);
  39.     stdout = setbuf(stdout, 1000);
  40.     
  41.     /* Use MICRO-C's more powerful '&&' to force a zero if !enough args */
  42.     switch((argc > 1) && toupper(*argv[1])) {
  43.         case 'E' :        /* Encode the file */
  44.             *(char*)stdout |= F_BINARY;        /* Convert stdout to BINARY */
  45.             while((i = getc(stdin)) != EOF)
  46.                 ++ftable[i];
  47.             rewind(stdin);
  48.  
  49.             /* Build table of most frequent characters */
  50.             for(i=0; i < TSIZE; ++i) {
  51.                 k = 0;
  52.                 for(j=1; j < 256; ++j)
  53.                     if(ftable[j] > ftable[k])
  54.                         k = j;
  55.                 ctable[i] = k;
  56.                 ftable[k] = 0; }
  57.  
  58.             /* Write the index table */
  59.             fwrite(ctable, TSIZE, stdout);
  60.  
  61.             /* Process the file */
  62.             while((i = getc(stdin)) != EOF) {
  63.                 for(j=0; j < TSIZE; ++j) {
  64.                     if(ctable[j] == i)
  65.                         break; }
  66.                 if(j < TSIZE) {        /* Write a token */
  67.                     do
  68.                         write_bit(1);
  69.                     while(j--);
  70.                     write_bit(0); }
  71.                 else {                /* Write the character */
  72.                     write_bit(0);
  73.                     for(k=0; k < 7; ++k) {
  74.                         write_bit(i & 0x01);
  75.                         i >>= 1; } } }
  76.  
  77.             /* Clean up output bits */
  78.             while(obyte)
  79.                 write_bit(0);
  80.             break;
  81.         case 'D' :        /* Decode the file */
  82.             *(char*)stdin  |= F_BINARY;    /* Convert stdin to BINARY */
  83.             fread(ctable, TSIZE, stdin);
  84.             while((i = read_bit()) != EOF) {
  85.                 j = 0;
  86.                 if(i) {    /* token */
  87.                     while((k = read_bit()) && (k != EOF))
  88.                         ++j;
  89.                     j = ctable[j]; }
  90.                 else {        /* Normal character */
  91.                     for(k=0; k < 7; ++k)
  92.                         j = (j >> 1) | read_bit();
  93.                     j >>= 1; }
  94.                 putc(j, stdout); }
  95.             break;
  96.         default:
  97.             abort("Use: HFTEXT E|D <input_file >output_file"); }
  98.  
  99.     fflush(stdout);
  100. }
  101.  
  102. /*
  103.  * Write a single bit to the output file
  104.  */
  105. write_bit(value)
  106.     int value;
  107. {
  108.     obyte = (obyte << 1) | value;
  109.     if(++ocount > 7) {
  110.         putc(obyte, stdout);
  111.         ocount = obyte = 0; }
  112. }
  113.  
  114. /*
  115.  * Read a single bit from the input file
  116.  */
  117. read_bit()
  118. {
  119.     int i;
  120.  
  121.     if(!ocount) {
  122.         if((obyte = getc(stdin)) == EOF)
  123.             return EOF;
  124.         ocount = 8; }
  125.     i = obyte;
  126.     obyte <<= 1;
  127.     --ocount;
  128.     return i & 0x80;
  129. }
  130.